package com.mlh.linkedlist;

/**
 * @author 缪林辉
 * @date 2024/8/21 15:44
 * @DESCRIPTION
 */
//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
public class 排序链表 {
    public ListNode method1(ListNode head) {
        if(head==null)return head;
        return merge(head);
    }
    public ListNode merge(ListNode head){
        if(head.next==null){
            return head;
        }
        ListNode fast=head.next,slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
        ListNode rightHead=slow.next;
        slow.next=null;
        ListNode leftHead = merge(head);
        rightHead = merge(rightHead);

        //底下就是合并两个有序链表的算法了
        ListNode sentry=new ListNode(-1),pre=sentry;
        while (leftHead!=null&&rightHead!=null){
            if(leftHead.val>rightHead.val){
                pre.next=rightHead;
                rightHead=rightHead.next;
            }else {
                pre.next=leftHead;
                leftHead=leftHead.next;
            }
            pre=pre.next;
        }
        if(leftHead==null){
            pre.next=rightHead;
        }else {
            pre.next=leftHead;
        }
        return sentry.next;
    }

    //使用了归并排序来解决该问题
    public ListNode mergePractice(ListNode head){
        if(head==null||head.next==null){
            return head;
        }
        ListNode slow=head,fast=head.next;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode merge1 = mergePractice(slow.next);
        slow.next=null;
        ListNode merge2 = mergePractice(head);
        //开始合并两个有序链表
        ListNode pre=new ListNode(),sentry=pre;
        while(merge1!=null&&merge2!=null){
            if(merge1.val> merge2.val){
                pre.next=merge2;
                merge2=merge2.next;
            }else{
                pre.next=merge1;
                merge1= merge1.next;
            }
            pre=pre.next;
        }
        if(merge1!=null){
            pre.next=merge1;
        }else{
            pre.next=merge2;
        }
        return sentry.next;
    }
}
